package com.cn.codebrush.数组.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/4/24 12:31
 * @Version 1.0
 */
public class No46全排列 {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(permute(nums));
    }

    /**
     * 回溯法
     * 注意与原来做的区别  增加了观察参数 visited
     */
    static List resList = new ArrayList();
    public static List<List<Integer>> permute(int[] nums) {
        int[] visited = new int[nums.length];
        permuteHelper(nums,new ArrayList(),visited);
        return resList;
    }

    public static void permuteHelper(int[] nums, List list,int[] visited) {
        if(list.size() == nums.length){
            resList.add(new ArrayList<>(list));
            return ;
        }

        for(int i=0;i<nums.length;i++){
            if(visited[i]==1){continue;}
            visited[i]=1;
            list.add(nums[i]);
            permuteHelper(nums,list,visited);
            visited[i]=0;
            list.remove(list.size()-1);
        }
    }
}
